Collective wisdom information growth in wikis and blogs.

Predictive State Representations for grounding human%2Drobot communication.

A Hybrid Model for Disease Spread and an Application to the SARS Pandemic

Comparing Prediction Market Structures%2C With an Application to Market Making
Ensuring sufficient liquidity is one of the key challenges for designers of prediction markets. Various market making algorithms have been proposed in the literature and deployed in practice, but there has been little effort to evaluate their benefits and disadvantages in a systematic manner. We introduce a novel experimental design for comparing market structures in live trading that ensures fair comparison between two different microstructures with the same trading population. Participants trade on outcomes related to a two-dimensional random walk that they observe on their computer screens. They can simultaneously trade in two markets, corresponding to the independent horizontal and vertical random walks. We use this experimental design to compare the popular inventory-based logarithmic market scoring rule (LMSR) market maker and a new information based Bayesian market maker (BMM). Our experiments reveal that BMM can offer significant benefits in terms of price stability and expected loss when controlling for liquidity; the caveat is that, unlike LMSR, BMM does not guarantee bounded loss. Our investigation also elucidates some general properties of market makers in prediction markets. In particular, there is an inherent tradeoff between adaptability to market shocks and convergence during market equilibrium. 1
Auctions
Combinatorial auctions can be used to reach efficient resource and task allocations in multiagent systems where the items are complementary. Determining the winners is NP-complete and inapproximable, but it was recently shown that optimal search algorithms do very well on average. This paper presents a more sophisticated search algorithm for optimal (and anytime) winner determination, including structural improvements that reduce search tree size, faster data structures, and optimizations at search nodes based on driving toward, identifying and solving tractable special cases. We also uncover a more general tractable special case, and design algorithms for solving it as well as for solving known tractable special cases substantially faster. We generalize combinatorial auctions to multiple units of each item, to reserve prices on singletons as well as combinations, and to combinatorial exchanges -- all allowing for substitutability. Finally, we present algorithms for determining the winners in these generalizations.
Anarchy%2C Stability%2C and Utopia Creating Better Matchings.
Matching markets have historically been an important topic in economics research. On the positive (descriptive) side, researchers have modeled everything ranging from marriage markets to labor markets using the framework of matching. Matching was also one of the first areas in which market design made a name for itself,
The effects of market%2Dmaking on price dynamics.
This paper studies market-makers, agents responsible for maintaining liquidity and orderly price transitions in markets. Market-makers include major firms making markets on global stock exchanges, as well as software agents that run behind the scenes on novel electronic markets like prediction markets. We use a sophisticated model of marketmaking to build richer agent-based models of markets and show how these models can be useful both in understanding properties of existing markets and in predicting the impacts of structural changes. For example, we show how competition among market-makers can lead to significantly faster price discovery following a jump in the true value of an asset. We also show that myopic profit-maximization, apart from leading to poor market quality, is sub-optimal even for a monopolistic market-maker. This observation leads to an interesting characterization of the market-maker’s explorationexploitation dilemma as a tradeoff between price discovery and profit-taking.
Adapting to a Market Shock Optimal Sequential Market%2DMaking.
We study the profit-maximization problem of a monopolistic market-maker who sets two-sided prices in an asset market. The sequential decision problem is hard to solve because the state space is a function. We demonstrate that the belief state is well approximated by a Gaussian distribution. We prove a key monotonicity property of the Gaussian state update which makes the problem tractable, yielding the first optimal sequential market-making algorithm in an established model. The algorithm leads to a surprising insight: an optimal monopolist can provide more liquidity than perfectly competitive market-makers in periods of extreme uncertainty, because a monopolist is willing to absorb initial losses in order to learn a new valuation rapidly so she can extract higher profits later. 1
Conference announcement the conference on auctions

Learning to trade with insider information.
This paper introduces algorithms for learning how to trade using insider (superior) information in Kyle’s model of financial markets. Prior results in finance theory relied on the insider having perfect knowledge of the structure and parameters of the market. I show here that it is possible to learn the equilibrium trading strategy when its form is known even without knowledge of the parameters governing trading in the model. However, the rate of convergence to equilibrium is slow, and an approximate algorithm that does not converge to the equilibrium strategy achieves better utility when the horizon is limited. I analyze this approximate algorithm from the perspective of reinforcement learning and discuss the importance of domain knowledge in designing a successful learning algorithm. 1
Finding Transport Proteins in a General Protein Database.
Abstract. The number of specialized databases in molecular biology is growing fast, as is the availability of molecular data. These trends necessitate the development of automatic methods for finding relevant information to include in specialized databases. We show how to use a comprehensive database (SwissProt) as a source of new entries for a specialized database (TCDB, the Transport Classification Database). Even carefully constructed keyword-based queries perform poorly in determining which SwissProt records are relevant to TCDB; we show that a machine learning approach performs well. We describe a maximum-entropy classifier, trained on SwissProt records, that achieves high precision and recall in cross-validation experiments. This classifier has been deployed as part of a pipeline for updating TCDB that allows a human expert to examine only about 2 % of SwissProt records for potential inclusion in TCDB. The methods we describe are flexible and general, so they can be applied easily to other specialized databases. 1
Two%2DSided Bandits and the Dating Market.
We study the decision problems facing agents in repeated matching environments with learning, or two-sided bandit problems, and examine the dating market, in which men and women repeatedly go out on dates and learn about each other, as an example. We consider three natural matching mechanisms and empirically examine properties of these mechanisms, focusing on the asymptotic stability of the resulting matchings when the agents use a simple learning rule coupled with an ɛ-greedy exploration policy. Matchings tend to be more stable when agents are patient in two different ways — if they are more likely to explore early or if they are more optimistic. However, the two forms of patience do not interact well in terms of increasing the probability of stable outcomes. We also define a notion of regret for the two-sided problem and study the distribution of regrets under the different matching mechanisms. 1
Learning and decision making for intention reconciliation.
Rational, autonomous agents must be able to revise their commitments in the light of new opportunities. They must decide when to default on commitments to the group in order to commit to potentially more valuable outside offers. The SPIRE experimental system allows the study of intention reconciliation in team contexts. This paper presents a new framework for SPIRE that allows for mathematical specification and provides a basis for the study of learning. Analysis shows that a reactive policy can be expected to perform as well as more complex policies that look ahead. We present an algorithm for learning when to default on group commitments based solely on observed values of group-related tasks and discuss the applicability of this algorithm in settings where multiple agents may be learning.
The influence of social norms and social consciousness on intention reconciliation.
Research on resource-bounded agents has established that rational agents need to be able to revise their commitments in light of new opportunities. In the context of collaborative activities, rational agents must be able to reconcile their intentions to do team-related actions with other, conflicting intentions. The SPIRE experimental system allows the process of intention reconciliation in team contexts to be simulated and studied. Initial work with SPIRE examined the impact of environmental factors and agent utility functions on individual and group outcomes in the context of one set of social norms governing collaboration. This paper extends those results by further studying the effect of environmental factors and the agents&#039; level of social consciousness and by comparing the impact of two different types of social norms on agent behavior and outcomes. The results show that agents operating under both sets of norms respond similarly to varying environmental factors, but that the choice of social norms influences the effectiveness of social consciousness and other aspects of agents&#039; utility functions. In experiments using heterogeneous groups of agents, both sets of norms were susceptible to the free-rider effect. However, the gains of the less responsible agents were minimal, suggesting that agent designers would have little incentive to design agents that deviated from the standard level of responsibility to the group.
Filters%2C Wrappers and a Boosting%2DBased Hybrid for Feature Selection.

